package javafoundation;



import java.util.ArrayList;
import java.util.Stack;

public class HuffmanTree {
    HuffmanTreeNode root;
    private String[] codes = new String[26];

    public HuffmanTree(HuffmanTreeNode[] a) throws EmptyCollectionException {
        HuffmanTreeNode parent = null;
        ArrayHeap<HuffmanTreeNode> heap;

        heap = new ArrayHeap<>();

        for(int i=0; i<a.length; i++) {
            heap.addElement(a[i]);
        }


        for(int i=0; i<a.length-1; i++) {
            HuffmanTreeNode left = heap.removeMin();
            HuffmanTreeNode right = heap.removeMin();


            parent = new HuffmanTreeNode(left.weight+right.weight,' ',left,right,null);
            left.parent = parent;
            right.parent = parent;

            heap.addElement(parent);
        }

        root = parent;
    }

    public String printTree() throws EmptyCollectionException {
        UnorderedListADT<HuffmanTreeNode> nodes =
                new ArrayUnorderedList();
        UnorderedListADT<Integer> levelList =
                new ArrayUnorderedList<Integer>();
        HuffmanTreeNode current;
        String result = "";
        int printDepth = this.getHeight()-1;
        int possibleNodes = (int)Math.pow(2, printDepth + 1);
        int countNodes = 0;

        nodes.addToRear(root);
        Integer currentLevel = 0;
        Integer previousLevel = -1;
        levelList.addToRear(currentLevel);

        while (countNodes < possibleNodes)
        {
            countNodes = countNodes + 1;
            current = nodes.removeFirst();
            currentLevel = levelList.removeFirst();
            if (currentLevel > previousLevel)
            {
                result = result + "\n\n";
                previousLevel = currentLevel;
                for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                    result = result + " ";
            }
            else
            {
                for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
                {
                    result = result + " ";
                }
            }
            if (current != null)
            {
                result = result + current.weight;
                nodes.addToRear(current.left);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(current.right);
                levelList.addToRear(currentLevel + 1);
            }
            else {
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                nodes.addToRear(null);
                levelList.addToRear(currentLevel + 1);
                result = result + " ";
            }
        }
        return result;
    }

    private int getHeight() {
        return height(root);
    }

    private int height(HuffmanTreeNode node)
    {
        if(node==null){
            return 0;
        }
        else {
            int leftTreeHeight = height(node.left);
            int rightTreeHeight= height(node.right);
            return leftTreeHeight>rightTreeHeight ? (leftTreeHeight+1):(rightTreeHeight+1);
        }
    }

    protected void inOrder( HuffmanTreeNode node,
                            ArrayList<HuffmanTreeNode> tempList)
    {
        if (node != null)
        {
            inOrder(node.left, tempList);
            if (node.element!=' ')
                tempList.add(node);

            inOrder(node.right, tempList);
        }
    }

    public String[] getEncoding() {
        ArrayList<HuffmanTreeNode> arrayList = new ArrayList();
        inOrder(root,arrayList);
        for (int i=0;i<arrayList.size();i++)
        {
            HuffmanTreeNode node = arrayList.get(i);
            String result ="";
            int x = node.element-'a';
            Stack stack = new Stack();
            while (node!=root)
            {
                if (node==node.parent.left)
                    stack.push(0);
                if (node==node.parent.right)
                    stack.push(1);

                node=node.parent;
            }
            while (!stack.isEmpty())
            {
                result +=stack.pop();
            }
            codes[x] = result;
        }
        return codes;
    }

    public HuffmanTreeNode getRoot() {
        return root;
    }
}
